class LRUCache:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.data = {}
        self.history = [] # 维护历史记录

    def get(self, key: int) -> int:
        value = self.data.get(key, -1)
        if value != -1:
            if key in self.history:
                self.history.remove(key)
            self.history.append(key)
        return value

    def put(self, key: int, value: int) -> None:
        if key not in self.history:
            self.history.append(key)
        else:
            self.history.remove(key)
            self.history.append(key)
        self.data[key] = value
        if len(self.data) > self.capacity:
            del self.data[self.history[0]]
            self.history =self.history[1:]

        
if __name__ == "__main__":
#     ["LRUCache","get","put","get","put","put","get","get"]
    # [[2],[2],[2,6],[1],[1,5],[1,2],[1],[2]]
    lru = LRUCache(2)
    lru.get(2)
    lru.put(2, 6)
    lru.get(1)
    lru.put(1, 5)
    lru.put(1, 2)
    lru.get(1)
    lru.get(2)
    # lru.put(1, 1)
    # lru.put(2, 2)
    # print(lru.get(1))
    # lru.put(3, 3)
    # print(lru.get(2))
    # lru.put(4, 4)
    # print(lru.get(1))
    # print(lru.get(3))
    # print(lru.get(4))